
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <math.h>

#include "globals.h"
#include "geometry.h"
#include "polygon.h"
#include "sweep.h"
#include "heap.h"
#include "link.h"
#include "voronoi.h"
#include "distance.h"
#include "sgidrawi.h"

static Pt	sweepTangent;
static Pgon	*sweepLine;

#define Increment	0.3

boolean	showSpokes;
boolean	showVoronoiEdges;
boolean showBottleneck;
boolean	showVoronoiVertices;
boolean	showDebugInfo;
boolean	showSweepSpokes;
boolean showFrontPierce;
boolean showPolygons;
boolean showAllFrontPierce;
boolean showSweepFront; static link_ref *swFront = NULL;
boolean jumpSweep;
boolean	autoDebug;

boolean	permitStep;
boolean	useFast;
boolean	demoPass;
boolean inSweep = False;

boolean dumpVorVertices;
boolean	dumpVorOrder;

boolean halting = False;
int		haltCount = 0;
int		haltLimit = 1;
int		haltMajorCount = 0;
int		haltMajorLimit = 1;

float	delayFactor = 1.0;

Real	sweepPosition = 0;
Real	circlex = 0, circley = 0, circlerad = 0;
Pgon	*distinguishedSite = NULL;
int		projectCount = 0;
int		spokecolour[100];
Pt		approxSpoke[3][100];
int		frontCount = 0;
Pt		frontPoints[4][100];
Pt		finalCheckSpokes[4];
boolean	finalLineDone = False;

/* -------------------------------------------------
   Advance declarations when needed.
   ------------------------------------------------- */

void advanceSweepLine(Real newPos);

/* -------------------------------------------------
   Support code for heaps.
   ------------------------------------------------- */

#ifndef M_PI
#define M_PI   3.14159265358979323846
#define M_PI_2 1.57079632679489661923
#define M_PI_4 0.78539816339744830962
#endif

SInt16
compareSpokeSlopes(spokeInfo *spoke1, spokeInfo *spoke2)
{
	register Real	x, y;
	Pt		pt1, pt2;
	double	th1, th2;

	/*	Want to sort by increasing angle of the middle spoke. */
	/*	Go for a brute-force solution for now.  Cocircularity
		shouldn't be happening _that_ often. */

	SubPoints(spoke1->attachment, spoke1->otherPt, pt1);
	SubPoints(spoke2->attachment, spoke2->otherPt, pt2);

	x = XVal(pt1); y = YVal(pt1);
	if (!Zero(x))
		th1 = atan((double)(y/x));
	else
		if (Less(y, 0)) th1 = -M_PI_2;
		else th1 = M_PI_2;
	if (Less(x, 0))  th1 += M_PI;
	if (Less(th1, 0)) th1 += 2*M_PI;

	x = XVal(pt2); y = YVal(pt2);
	if (!Zero(x))
		th2 = atan((double)(y/x));
	else
		if (Less(y,0)) th2 = -M_PI_2;
		else th2 = M_PI_2;
	if (Less(x, 0))  th2 += M_PI;
	if (Less(th2, 0)) th2 += 2*M_PI;

	if (Zero(th1 - th2)) return (0);
	else return (Less(th1, th2) ? -1 : 1);
}

SInt16
compareHeapKeys(Ptr arg1, Ptr arg2)
{
	register Real			x1, x2;

	if ((arg1 == NULL) || (arg2 == NULL)) {
		if ((arg1 == NULL) || (arg2 == NULL))
			return (0);
		else if ((arg1 == NULL) && (arg2 != NULL))
			return (1);
		else if ((arg1 != NULL) && (arg2 == NULL))
			return (-1);
	}

	x1 = XVal(((scheduleInfo *)(arg1))->eventPt);
	x2 = XVal(((scheduleInfo *)(arg2))->eventPt);

	if (Less(x1, x2))
		return (-1);
	else if (Greater(x1, x2))
		return (1);
	else {
		register Real	y1, y2;

		y1 = YVal(((scheduleInfo *)(arg1))->eventPt);
		y2 = YVal(((scheduleInfo *)(arg2))->eventPt);

		if (Greater(y1, y2)) return (-1);
		else if (Less(y1, y2)) return (1);
		else 
			return(compareSpokeSlopes(&(((scheduleInfo *)arg1)->midSpoke), 
				&(((scheduleInfo *)arg2)->midSpoke)));
	}
}

/* -------------------------------------------------
   Routines for drawing the sweep animation.
   ------------------------------------------------- */

void
highlightSites()
{
	if (autoDebug == True) 
		if (distinguishedSite != NULL) 
			printPoly (PolyHighlight, distinguishedSite);
}

void
drawSweepFront(link_ref *front)
{
#ifdef Graphics
	Pt			lowerVoronoi, upperVoronoi, event;
	link_node	*lowerArc, *upperArc;
	frontInfo	*lower, *upper;
	boolean		what, ignore;
	spokeInfo	spoke;
	Pt			upperCorner, lowerCorner;
	Real		pgonDist, sweepDist;

	upperCorner.w = 1.0;
	upperCorner.x = -20.5;
	upperCorner.y = 120.5;
	
	lowerCorner.w = 1.0;
	lowerCorner.x = -20.5;
	lowerCorner.y = -20.5;

	if ((front != NULL)  && (inSweep == True)) {
		upperArc = front->head;
		if (upperArc != NULL) {
			what = getLinkInfo(upperArc, (void **)(&upper));
			PointAssign(upperVoronoi, upperCorner);
			lowerArc = nextLink(front, upperArc);
			/*	Figure out where my upper corner really lies. */

			findSpoke(&upperCorner, upper->generator, &spoke);
			squarePointDistance(&upperCorner, &(spoke.attachment),
				&pgonDist);
			sweepDist = (XVal(upperCorner) - sweepPosition) *
						(XVal(upperCorner) - sweepPosition);

			if (sweepDist > pgonDist) {
				/* Crawl along the top of the window. */
			}
			else {
				/* Crawl along the left edge of the window. */
			}

			while (lowerArc != NULL) {
				what = getLinkInfo(lowerArc, (void **)(&lower));
				ignore = voronoiVertex (lower->generator, sweepLine, 
					upper->generator, &lowerVoronoi, &event, &spoke);

				drawBisector(upper->generator, sweepLine, &lowerVoronoi, 
					&upperVoronoi, SweepfrontCol, False);

				upperArc = lowerArc;
				upper = lower;
				lowerArc = nextLink(front, lowerArc);
				PointAssign(upperVoronoi, lowerVoronoi);
			}

			PointAssign(lowerVoronoi, lowerCorner);
			drawBisector(upper->generator, sweepLine, &lowerVoronoi, 
					&upperVoronoi, SweepfrontCol);
		}
	}
#endif
}

void
redrawSweepStatus()
{
#ifdef Graphics
	int		j;

	if (autoDebug == True) {
		drawline (SweeplineCol, (float)(sweepPosition), 
					(float)(-1*SweepLimits), 
					(float)(sweepPosition), (float)SweepLimits);

		if (showSweepFront == True)
			drawSweepFront(swFront);
		if (!Zero(circlerad))
			drawcircle(CircleEventCol, circlex, circley, circlerad);
		if (distinguishedSite != NULL) {
			for (j = 0; j < projectCount; j++) {
				drawline (spokecolour[j], 
					(float)(XVal(approxSpoke[0][j])), 
					(float)(YVal(approxSpoke[0][j])), 
					(float)(XVal(approxSpoke[1][j])),
					(float)(YVal(approxSpoke[1][j])));
				drawline (spokecolour[j], 
					(float)(XVal(approxSpoke[0][j])), 
					(float)(YVal(approxSpoke[0][j])), 
					(float)(XVal(approxSpoke[2][j])),
					(float)(YVal(approxSpoke[2][j])));
			}
			if (showSweepSpokes == True) {
				for (j = 0; j < frontCount; j++) {
					drawline (SweepSpokeCol,
						(float)(XVal(frontPoints[0][j])), 
						(float)(YVal(frontPoints[0][j])), 
						(float)(XVal(frontPoints[1][j])), 
						(float)(YVal(frontPoints[1][j])));
					drawline (SweepSpokeCol,
						(float)(XVal(frontPoints[0][j])), 
						(float)(YVal(frontPoints[0][j])), 
						(float)(XVal(frontPoints[2][j])), 
						(float)(YVal(frontPoints[2][j])));
					drawline (SweepSpokeCol,
						(float)(XVal(frontPoints[0][j])), 
						(float)(YVal(frontPoints[0][j])), 
						(float)(XVal(frontPoints[3][j])), 
						(float)(YVal(frontPoints[3][j])));
				}
			}
			if (finalLineDone == True) {
				for (j = 1; j <= 3; j++) {
					drawline (BinSearchFinCol, 
					(float)(XVal(finalCheckSpokes[0])), 
					(float)(YVal(finalCheckSpokes[0])), 
					(float)(XVal(finalCheckSpokes[j])),
					(float)(YVal(finalCheckSpokes[j])));
				}
			}
			if (showPolygons == True) 
				printPoly (PolyHighlight, distinguishedSite);
		}
	}
#endif
}

void
waitForStep(void)
{
#ifdef Graphics
	int		i;

	/*	I want a delay here somehow */
	if (autoDebug == True) {
		if (halting == True) {
			haltMajorCount += 1;
			while (haltMajorCount == haltMajorLimit) 
				fl_check_forms();
			haltCount = 0;
			haltLimit = 1;
		}
		else {
			for (i = 0; i < 250*delayFactor; i++) {
				fl_check_forms();
			}
		}
	}
#endif
}

void
waitForSubStep(void)
{
#ifdef Graphics
	int		i;

	/*	I want a delay here somehow */
	if (autoDebug == True) {
		if (halting == True) {
			haltCount += 1;
			while (haltCount == haltLimit) 
				fl_check_forms();
		}
		else {
			for (i = 0; i < 175*delayFactor; i++) {
				fl_check_forms();
			}
		}
	}
#endif
}

#ifdef Graphics
void
clearAnimationInfo()
{
	/*	Kill off any sweep event information for refreshes. */

	circlerad = 0;
	distinguishedSite = NULL;
	projectCount = 0;
	frontCount = 0;
	finalLineDone = False;
}
#else
#define clearAnimationInfo() {}
#endif

#ifdef Graphics
void
animateSweepLine(scheduleInfo *nextPoly, scheduleInfo *nextCircle)
{
	Real			nextStop;
	int				delay;
	FL_OBJECT		*obj;

	/*	Give the user time to adjust something on the screen. */

	obj = fl_check_forms();
		
	if ((nextCircle == NULL) || ((nextPoly != NULL) && 
		(!Less(XVal(nextCircle->eventPt), XVal(nextPoly->eventPt))))) 
		nextStop = XVal(nextPoly->eventPt);
	else
		nextStop = XVal(nextCircle->eventPt);

	if ((jumpSweep == False) &&(demoPass == True) && 
		((showDebugInfo == True) || (autoDebug == True))) {
		while (sweepPosition <= nextStop) {
			advanceSweepLine(sweepPosition);
			redraw();

			for (delay = 0; 
				(delay < 10*delayFactor) && (autoDebug == True); 
				delay++) {
				fl_check_forms();
			}
			sweepPosition = (sweepPosition > 120.5 ? 
					nextStop + Increment : 
					sweepPosition + Increment);
		}
		redraw();
	}
	else {
			sweepPosition = nextStop + Increment; 
	}
}
#else
#define animateSweepLine(A,B) {}
#endif

/* -------------------------------------------------
   Debugging routines. 
   ------------------------------------------------- */

#if defined(SHOW_HEAP) || defined(SHOW_FRONT)
void
steadyStateDebuggingInfo(link_ref *front, HEAP_Heap polySched, 
   HEAP_Heap circSched)
{
	link_node	*nd;
	frontInfo	*info;
	boolean		what;
	int			i;

#ifdef SHOW_HEAP
	printf ("Circle Heap is: \n");
	HEAP_Print (circSched);
	printf ("\n");
	printf ("Site Heap is: \n");
	HEAP_Print (polySched);
	printf ("\n");
#endif

#ifdef SHOW_FRONT
	printf ("show the front sequence:\n");
	nd = front->head;
	while (nd != NULL) {
		what = getLinkInfo(nd, (void **)(&info));
		printf ("%5.2f %5.2f (%d %d %d)", 
			XVal(info->generator->points[0]),
			YVal(info->generator->points[0]), 
			info->atTopRef, info->deathRef, info->atBottomRef);
		for (i = 0; i < info->topCount; i++)
			printf (" %d", info->topVor[i]);
		printf (" / ");
		for (i = 0; i < info->bottomCount; i++)
			printf (" %d", info->bottomVor[i]);
		printf ("\n");
		nd = nextLink(front, nd);
	}
#endif
}
#else
#define steadyStateDebuggingInfo(A,B,C) {}
#endif

#ifdef SHOW_FRONT
void
showVerticesDebugging(int numPoly, Pgon **polyList)
{
	int	i, j;

	for (i = 0; i < numPoly; i++) {
		printf ("%f %f (%d): ", XVal(polyList[i]->points[0]),
			YVal(polyList[i]->points[0]), polyList[i]->voronoiCount);
		for (j = 0; j < polyList[i]->voronoiCount; j++) {
			printf ("%d ", polyList[i]->voronoiList[j]);
		}
		printf ("\n");
	}
}
#else
#define showVerticesDebugging(A,B) {}
#endif

/* -------------------------------------------------
   Pseudo data structures for the sweep front and
   schedules.
   ------------------------------------------------- */

void
startSchedule(int sizeEst)
{
}

scheduleInfo
*newSchedule()
{
	return ((scheduleInfo *) malloc(sizeof(scheduleInfo)));
}

void
killSchedule(scheduleInfo **sched)
{
	free(*sched);
	*sched = NULL;
}

void
endSchedule()
{
}

void
startFront(int sizeEst)
{
}

frontInfo
*newFront()
{
	return ((frontInfo *) malloc(sizeof(frontInfo)));
}

void
killFront(frontInfo **front)
{
	free(*front);
	*front = NULL;
}

void
endFront()
{
}

static int	pointCount = 0, maxPointCount;
static Pt	*ptList = NULL;

void
readyPointStore(int size)
{
	pointCount = 0;
	maxPointCount = size;

	ptList = (Pt *) FA_Alloc(sizeof(Pt), size, "Points");
}

void
endPointStore()
{
}

Pt 
*reservePointStore()
{
	Pt	*retVal;

	if (pointCount < maxPointCount) {
		retVal = (Pt *) _FA_new(&ptList);
		pointCount += 1;
		return (retVal);
	}
	else
		return (NULL);
}

void
releasePointStore(Pt **pt)
{
	_FA_dispose(pt, &ptList);
	*pt = NULL;
}


/* -------------------------------------------------
   The actual sweep workhorse routines.
   ------------------------------------------------- */

boolean 
scheduleNewSites(HEAP_Heap schedule, Pgon **polyList, int numPoly)
{
	int		i;
	HEAP_HeapId	ignore;
	boolean	succeed;
	Pgon	*curPol;
	scheduleInfo	*info;
	
	succeed = True;
	for (i = 0; i < numPoly; i++){
		info = newSchedule();
		if (info != NULL) {
			curPol = polyList[i];
			PointAssign(info->eventPt, (curPol->points[curPol->leftmost]));
			info->poly[0] = curPol;
			succeed |= HEAP_Add (schedule, (Ptr) info, &ignore);
		}
		else
			succeed = False;
	}
	return (succeed);
}

void
findProjection(frontInfo *info, Pt *breakPt, int colour, 
	boolean showProject, Pt *imagePt)
{
	Line	sweepline, shootline;
	Pt		frontPt, *leftPt, *rightPt;
	Line	spokeline, perp;

#ifdef DEBUG_SWEEP
	printf ("swp: find projection for arc %2.2f %2.2f\n",
		XVal(info->generator->points[0]),
		YVal(info->generator->points[0]));
#endif

	leftPt = &(info->generator->points[info->generator->leftmost]);
	rightPt = &(info->generator->points[info->generator->rightmost]);

	/*	Set up the sweepline */

	sweepline.w = XValPtr(breakPt);
	sweepline.x = -1.0;
	sweepline.y = 0.0;

	if (Less(XValPtr(rightPt), XValPtr(breakPt))) {

		/*	The projection point is the intersection of the sweepline and
			any line that goes through the front arc. */

		IntersectionOf(&sweepline, &(info->lineThroughFrontArc), imagePt);

#ifdef DEBUG_SWEEP
		printf ("swp: projected point for %3f %3f is %3.2f %3.2f\n", 
			XVal(info->generator->points[0]),
			YVal(info->generator->points[0]),
			XValPtr(imagePt), YValPtr(imagePt));
#endif

#ifdef Graphics
			if ((demoPass == True) && (showDebugInfo == True) &&
				(showProject == True)) {
				LineOf(&((info->spoke).otherPt),&((info->spoke).attachment), 
					&spokeline);
				perpendicularLine(imagePt, &sweepline, &perp);
				if ((Zero(perp.x)) && (Zero(spokeline.x))) {
					MidPoint(*imagePt, (info->spoke).attachment, frontPt);
				}
				else {
					IntersectionOf(&perp, &spokeline, &frontPt);
				}

				/*	Remember this set of spokes for displaying. */

				spokecolour[projectCount] = colour;
				PointAssign(approxSpoke[0][projectCount], frontPt);
				PointAssign(approxSpoke[1][projectCount], 
								(info->spoke).attachment);
				PointAssign(approxSpoke[2][projectCount], *imagePt);
				projectCount ++;
			}
#endif
	}
	else {
		if (Equal(XValPtr(rightPt), XValPtr(leftPt))) {

			/*	We have a single point or a vertical line -- the point
				itself can be the image on the sweepline. */

			PointAssignPtr(imagePt, leftPt);
		}
		else {
			/*	We actually have a polygon, not just a single point. */
			LineOf(rightPt, leftPt, &shootline);
			IntersectionOf(&sweepline, &shootline, imagePt);
		}
	}
}

link_node
*findStdBrokenArc(Pt *matchPoint, link_ref *front)
{
	link_node	*current, *prev, *high, *low;
	Pt			vorPt, eventPt;
	frontInfo	*info, *upper, *lower;
	boolean		dontCare;
	spokeInfo	sweepSpoke;
	Real		compareHeight;
#ifdef Graphics
	Pt			attach;
#endif

#ifdef DEBUG_SWEEP
	printf ("swp: find broken arc for %3.2f %3.2f\n",
		XValPtr(matchPoint), YValPtr(matchPoint));
#endif

	compareHeight = YValPtr(matchPoint);

	/*	Start a binary search along the front to find the interval
		in which 'matchPoint' belongs. */

	current = binSearchLink (front, NULL, UP);
	prev = NULL;

	/*	Divide the sweepline into the segments for the sweep front. */

	while (current != NULL) {
		dontCare = getLinkInfo(current, (void **)(&info));
		if ((prev = prevLink(front, current)) == NULL) {
			high = current;
			low = nextLink(front, current);
		}
		else {
			high = prev;
			low = current;
		}

		if (low != NULL) {

			/*	Find the intersection point in the sweep front. */

			dontCare = getLinkInfo(high, (void **)(&upper));
			dontCare = getLinkInfo(low, (void **)(&lower));

			dontCare = voronoiVertex(lower->generator, sweepLine, 
				upper->generator, &vorPt, &eventPt, &sweepSpoke);

#ifdef Graphics
			if ((demoPass == True) && ((showDebugInfo == True) ||
				(autoDebug == True)) && 
				((showFrontPierce == True) || (showSweepSpokes == True))) {
				waitForSubStep();
				ptNearestPgon (&vorPt, sweepLine, &attach);
				finalLineDone = True;
				PointAssign(finalCheckSpokes[0], vorPt);
				PointAssign(finalCheckSpokes[1], attach);
				ptNearestPgon (&vorPt, lower->generator, &attach);
				PointAssign(finalCheckSpokes[2], attach);
				ptNearestPgon (&vorPt, upper->generator, &attach);
				PointAssign(finalCheckSpokes[3], attach);
				redraw();
			}
#endif

			/*	Since the sweepline is infinite, we must have
				a finite Voronoi vertex and the spoke to the 
				sweeepline is valid. */

			if (Greater(compareHeight, YVal(sweepSpoke.attachment))) 
				current = binSearchLink (front, current, UP);
			else 
				current = binSearchLink (front, current, DOWN);

		}
		else {
			prev = current;
			current = NULL;
		}
	}

	return (prev);
}


link_node
*findBrokenArc(Pt *matchPoint, link_ref *front)
{
	link_node	*current, *prev, *high, *low;
	Pt			project, vorPt, eventPt;
	int			direction;
	frontInfo	*info, *prevInfo;
	frontInfo	*upper, *lower;
	boolean		dontCare;
	spokeInfo	sweepSpoke;
	Real		compareHeight;
#ifdef Graphics
	Pt			attach;
#endif

#ifdef DEBUG_SWEEP
	printf ("swp: find broken arc for %3.2f %3.2f\n",
		XValPtr(matchPoint), YValPtr(matchPoint));
#endif

	compareHeight = YValPtr(matchPoint);

	/*	Start a binary search along the front to find the interval
		in which 'matchPoint' belongs. */

	current = binSearchLink (front, NULL, UP);
	prev = NULL;
	prevInfo = NULL;

	/*	Divide the sweepline into the segments for the sweep front. */

	while (current != NULL) {
		if ((demoPass == True) && (showDebugInfo == True) &&
			((showSweepSpokes == True) || (showFrontPierce == True) || 
			(showAllFrontPierce == True))) {
			waitForSubStep();
		}
		dontCare = getLinkInfo(current, (void **)(&info));
		findProjection(info, matchPoint, BinSearch2Col, showFrontPierce,
			&project);
#ifdef graphics
		if (((autoDebug == True) || (showDebugInfo == True)) &&
			((showSweepSpokes == True) || (showFrontPierce == True) || 
			(showAllFrontPierce == True)))
			redraw();
#endif
		if (Greater(YVal(project), compareHeight)) 
			direction = DOWN;
		else 
			direction = UP;
		prev = current;
		prevInfo = info;
		current = binSearchLink (front, prev, direction);
#ifdef DEBUG_SWEEP
		printf ("swp: binary search goes %s\n", 
			(direction == DOWN ? "down" : "up"));
#endif
	}

	if (prev == NULL) {
		/*	There are no arcs in the front -- simple to add the first one */
		current = NULL;
	}
	else {
		if (((direction == DOWN) && (nextLink(front, prev) == NULL)) || 
			((direction == UP) && (prevLink(front, prev) == NULL))) {
			/*	We are intersecting one of the tail extremes. */

			current = prev;
		}
		else {
			/*	An arc needs to be split.  We have narrowed the possibilities
				down to two arcs.  Find the real culprit. */

			if (direction == DOWN) {
				high = prev;
				upper = prevInfo;
				low = nextLink(front, prev);
				dontCare = getLinkInfo(low, (void **)(&lower));
			}
			else {
				high = prevLink(front, prev);
				dontCare = getLinkInfo(high, (void **)(&upper));
				low = prev;
				lower = prevInfo;
			}

			dontCare = voronoiVertex(lower->generator, sweepLine, 
				upper->generator, &vorPt, &eventPt, &sweepSpoke);
#ifdef DEBUG_SWEEP
			printf ("swp: voronoi vertex between (%2.2f %2.2f) and "
				"(%2.2f %2.2f) is %3.2f %3.2f\n",
				XVal(upper->generator->points[0]),
				YVal(upper->generator->points[0]),
				XVal(lower->generator->points[0]),
				YVal(lower->generator->points[0]),
				XVal(vorPt), YVal(vorPt));
#endif
#ifdef Graphics
			if ((demoPass == True) && (showDebugInfo == True) &&
				((showSweepSpokes == True) || (showFrontPierce == True))) {
				waitForSubStep();
				ptNearestPgon (&vorPt, sweepLine, &attach);
				finalLineDone = True;
				PointAssign(finalCheckSpokes[0], vorPt);
				PointAssign(finalCheckSpokes[1], attach);
				ptNearestPgon (&vorPt, lower->generator, &attach);
				PointAssign(finalCheckSpokes[2], attach);
				ptNearestPgon (&vorPt, upper->generator, &attach);
				PointAssign(finalCheckSpokes[3], attach);
				redraw();
			}
#endif


			/*	Since the sweepline is infinite, we must have
				a finite Voronoi vertex and the spoke to the 
				sweeepline is valid. */

			if (Greater(compareHeight, YVal(sweepSpoke.attachment))) 
				current = high;
			else 
				current = low;

		}
	}
	return (current);
}

/*	Given a spoke from centre point fromPt to its attachment point
	toPt, find the line that goes from the attachment point through
	the front arc to the sweepline. */

void
getFrontPiercingLine(Pt *fromPt, Pt *toPt, Line *line)
{
	Pt		exitPt;
	Line	shootline;

	/*	Get the line that shoots across the sweepline.  What we do
		is find the line through the convex distance function, from
		the place tangent to "info" to the tangency point of the
		sweepline.  The line we want is parallel to that one.  Then,
		we translate this line to the desired position.  */

	getExitPoint(fromPt, toPt, &exitPt);
	LineOf(&sweepTangent, &exitPt, &shootline);

	/*	shootline has the correct slope, but it is positioned
		relative to the distance function centred at 0.  Finish
		by shifting its y-intercept so the line goes through the 
		"toPt". */

	/*	All parallel lines have equal .x and .y components.
		We only need to adjust the y-intercept. */

	line->w = (Coordinate) -(toPt->y * shootline.y + toPt->x * shootline.x);
	line->x = (Coordinate) shootline.x * toPt->w;
	line->y = (Coordinate) shootline.y * toPt->w;
}

/*	Divide front arc "broken" */

void 
splitFrontArc(link_ref *front, HEAP_Heap schedule, link_node *broken, 
	Pgon *splitter, link_node **topHalf, link_node **newArc, 
	link_node **bottomHalf)
{
	frontInfo	*top, *middle, *bottom;
	boolean		dontCare;
	scheduleInfo	*schedData;
	int			i;

#ifdef DEBUG_SWEEP
	printf ("swp: split front arc .. front exists\n");
#endif
	/*	We can re-use the site "broken" so we only need two new
		link nodes. */

	dontCare = getLinkInfo (broken, (void **)(&top));
	middle = newFront();
	bottom = newFront();

	/*	The top and the bottom come from the same polygon. 
		The top->atBottomRef doesn't change since we are re-using
		the node for "broken" as the top arc. */

	bottom->generator = top->generator;
	bottom->deathRef = HEAP_NullHeapId;
	bottom->atTopRef = top->atTopRef;
	bottom->atBottomRef = HEAP_NullHeapId;

	top->atTopRef = HEAP_NullHeapId;
	top->deathRef = HEAP_NullHeapId;

	/*	Load the middle arc. */

	middle->generator = splitter;
	middle->deathRef = HEAP_NullHeapId;
	middle->atTopRef = HEAP_NullHeapId;
	middle->atBottomRef = HEAP_NullHeapId;

	middle->prev = NULL;
	middle->next = NULL;
	middle->topCount = 0;
	middle->bottomCount = 0;

	/*	Set up a spoke for the new polygon that will come into effect
		as soon as the sweepline passes the rightmost point of the site. */

	PointAssign(middle->spoke.attachment,splitter->points[splitter->rightmost]);
	AddPoints(splitter->points[splitter->rightmost], sweepTangent,
		middle->spoke.otherPt);
	middle->spoke.attachPolygon = splitter;
	middle->spoke.attachIndex = splitter->rightmost;
	getFrontPiercingLine(&(middle->spoke.otherPt),
		&(middle->spoke.attachment),
		&(middle->lineThroughFrontArc));

	/*	Splice these new items into the front.  The node corresponding
		to "top" is already in the front. */

	*topHalf = broken;
	dontCare = addAfterLink(front, *topHalf, middle, newArc);
	dontCare = addAfterLink(front, *newArc, bottom, bottomHalf);

	/*	Link the split front together into the linked list*/

	bottom->next = top->next;
	top->next = bottom;
	bottom->prev = top;
	if (bottom->next != NULL)
		bottom->next->prev = bottom;

	/*	And transfer some of the Voronoi vertices already found. */

	for (i = 0; i < top->bottomCount; i++) {
		bottom->bottomVor[i] = top->bottomVor[i];
	}
	bottom->bottomCount = top->bottomCount;
	bottom->topCount = 0;
	top->bottomCount = 0;

	/*	When we split "broken", the scheduled circle event with "broken"
		at the top doesn't change, but we do need to change the front
		arc reference for that event. */

	if (HEAP_PeekNamed (schedule, bottom->atTopRef, 
		(Ptr *)(&schedData)) == True) {
		schedData->frontArcs[0] = *bottomHalf;
	}
}

void
copySpoke(spokeInfo *from, spokeInfo *to)
{
	to->attachPolygon = from->attachPolygon;
	to->attachIndex = from->attachIndex;
	PointAssign(to->attachment, from->attachment);
	PointAssign(to->otherPt, from->otherPt);
}

/*	Schedule the circle event for the three consecutive front arcs
	starting at "start".  Also, store the spoke that pokes through
	the front arc for the middle/second front arc.  We assume that
	there are three consecutive arcs to work with. */

void
scheduleCircle (HEAP_Heap schedule, link_ref *front, link_node *start, 
	Real sweepPos)
{
	link_node	*middle, *last;
	frontInfo	*arc1, *arc2, *arc3;
	Pgon		*first, *second, *third;
	Pt			vorPoint, eventPt;
	boolean		dontCare;
	HEAP_HeapId		schedKey;
	scheduleInfo	*circleEvent;

#ifdef DEBUG_SWEEP
	printf ("swp: schedule circle, sweepline is at %f\n", sweepPos);
#endif

	/*	Get pointers to each of the front arcs */

	middle = nextLink(front, start);
	last = nextLink(front, middle);

	dontCare = getLinkInfo(start, (void **)(&arc1));
	dontCare = getLinkInfo(middle, (void **)(&arc2));
	dontCare = getLinkInfo(last, (void **)(&arc3));

	/*	Extract the polygons involved in the operation. */

	first = arc1->generator;
	second = arc2->generator;
	third = arc3->generator;

	/*	Get the appropriate Voronoi vertex and spokes. */

	if (voronoiVertex(first, second, third, &vorPoint, &eventPt, 
		&(arc2->spoke)) == True) {

		circleEvent = newSchedule();
		PointAssign(circleEvent->eventPt, eventPt);

		PointAssign(circleEvent->eventCentre, vorPoint);

		circleEvent->poly[0] = first;
		circleEvent->poly[1] = second;
		circleEvent->poly[2] = third;

		circleEvent->frontArcs[0] = start;
		circleEvent->frontArcs[1] = middle;
		circleEvent->frontArcs[2] = last;

		copySpoke(&(arc2->spoke), &(circleEvent->midSpoke));

#ifdef DEBUG_SWEEP
	printf ("swp: circle scheduled at x = %2.2f y = %2.2f for (%2.f %2.f) "
		"(%2.f %2.f) (%2.f %2.f) at sweep x=%2.2f\n", 
		XVal(vorPoint), YVal(vorPoint),
		XVal(first->points[0]), YVal(first->points[0]),
		XVal(second->points[0]), YVal(second->points[0]),
		XVal(third->points[0]), YVal(third->points[0]),
		XVal(circleEvent->eventPt));
#endif

		dontCare = HEAP_Add(schedule, (Ptr) circleEvent, &schedKey);
	}
	else {
#ifdef DEBUG_SWEEP
		printf ("swp: could not schedule circle for "
			"(%2.f %2.f) (%2.f %2.f) (%2.f %2.f)\n", 
			XVal(first->points[0]), YVal(first->points[0]),
			XVal(second->points[0]), YVal(second->points[0]),
			XVal(third->points[0]), YVal(third->points[0]));
#endif
		schedKey = HEAP_NullHeapId;
	}

	arc1->atTopRef = schedKey;
	arc2->deathRef = schedKey;
	arc3->atBottomRef = schedKey;

	getFrontPiercingLine(&(arc2->spoke.otherPt), &(arc2->spoke.attachment),
		&(arc2->lineThroughFrontArc));
}

void
tryToSchedule(link_ref *front, HEAP_Heap schedule, link_node *middle, 
	Real sweepPos)
{
	frontInfo	*info, *nbInfo;
	boolean		dontCare;
	link_node	*pred, *suc;
	Pt			start, end, *tanPt;
	Line		tangent, perp;
	int			headIdx, tailIdx;

	pred = prevLink (front, middle);
	suc = nextLink (front, middle);

	if ((pred != NULL) && (suc != NULL)) {
		scheduleCircle (schedule, front, pred, sweepPos);
	}
	else {
		if (middle != NULL) {
			dontCare = getLinkInfo(middle, (void **)(&info));
			if (pred != NULL) {
				dontCare = getLinkInfo(pred, (void **)(&nbInfo));
				outerCommonTangent(info->generator, nbInfo->generator,
					&start, &end, &headIdx, &tailIdx);
					tanPt = &start; 
			}
			else {
				dontCare = getLinkInfo(suc, (void **)(&nbInfo));
				outerCommonTangent(nbInfo->generator, info->generator,
					&start, &end, &headIdx, &tailIdx);
					tanPt = &end; 
			}

			LineOf(&start, &end, &tangent);
			perpendicularLine(tanPt, &tangent, &perp);

			PointAssign(info->spoke.attachment, *tanPt);

			info->deathRef = HEAP_NullHeapId;
			if (pred == NULL)
				nbInfo->atBottomRef = HEAP_NullHeapId;
			else
				nbInfo->atTopRef = HEAP_NullHeapId;

			awayPoint(&perp, &tangent, &(info->spoke.otherPt));
			getFrontPiercingLine(&(info->spoke.otherPt), 
					&(info->spoke.attachment),
					&(info->lineThroughFrontArc));
		}
	}
}

void
findSweepFrontLines(Pt *matchPoint, link_ref *front)
{
	Pt			imagePt;
	link_node	*runner, *trail;
	frontInfo	*info, *trailInfo;
	boolean		dontCare;
	spokeInfo	spoke, topSpoke, bottomSpoke;
	Pt			vorPoint, eventPoint;

	/*	Set up a sweep line as a polygon. */

	runner = front->head;
	trail = NULL;
	while (runner != NULL) {
		/*	Set up the lines crossing the sweep front. */

		dontCare = getLinkInfo (runner, (void **)(&info));
		findProjection(info, matchPoint, BinSearchCol, 
			showAllFrontPierce, &imagePt);

		/*	Set up the actual spokes for the sweep front. */

		if (trail != NULL) {
			if (voronoiVertex(info->generator,
				sweepLine, trailInfo->generator, &vorPoint, &eventPoint, 
				&(spoke)) == True) {
				findSpoke(&vorPoint, info->generator, &topSpoke);
				findSpoke(&vorPoint, trailInfo->generator, &bottomSpoke);
				PointAssign(frontPoints[0][frontCount], vorPoint);
				PointAssign(frontPoints[1][frontCount], topSpoke.attachment);
				PointAssign(frontPoints[2][frontCount], spoke.attachment);
				PointAssign(frontPoints[3][frontCount], bottomSpoke.attachment);
				frontCount++;
			}
		}

		trail = runner;
		trailInfo = info;
		runner = nextLink (front, runner);
	}
}

void
processNewSite(scheduleInfo *item, link_ref *front, HEAP_Heap schedule)
{
	link_node	*broken, *topHalf, *newArc, *bottomHalf;
	Pt			matchPoint;
	boolean		dontCare;
	frontInfo	*info;
	scheduleInfo	*schedData;
	Pgon		*poly;

#ifdef DEBUG_FLOW
	printf ("swp: New Site at x = %3.2f\n", (float) XVal(item->eventPt));
#endif

	/*	Extract the point that crossed the sweep line */

	poly = item->poly[0];
	PointAssign(matchPoint, poly->points[poly->leftmost]);
#ifdef Graphics
	if ((demoPass == True) && ((autoDebug == True) || (showDebugInfo == True))){
		distinguishedSite = poly;
		printPoly (PolyHighlight, poly);
		if (showAllFrontPierce == True)
			findSweepFrontLines(&matchPoint, front);
		redraw();
	}
#endif

#ifdef DEBUG_SWEEP
	printf ("swp: add arc to an existing sweep front\n");
#endif
	/*	Find the front arc that is split by the new point */

	if (useFast == True) 
		broken = findBrokenArc(&matchPoint, front);
	else
		broken = findStdBrokenArc(&matchPoint, front);

	/*	Delete the associated death vertex for the broken arc */

	dontCare = getLinkInfo(broken, (void **)(&info));
#ifdef DEBUG_SWEEP
	printf ("swp: broken arc is %2.2f %2.2f\n",
		XVal(info->generator->points[0]), YVal(info->generator->points[0]));
#endif
	if (HEAP_PopNamed (schedule,info->deathRef,(Ptr *)(&schedData)) == True){
#ifdef DEBUG_SWEEP
		printf ("swp: unschedule circle event at %3.2f %3.2f\n",
			XVal(schedData->eventCentre), YVal(schedData->eventCentre));
#endif
		killSchedule(&schedData);
	}

	/*	Split the broken arc with the new point */

	splitFrontArc(front, schedule, broken, poly, &topHalf, &newArc, 
		&bottomHalf);

	/*	Schedule new circle events for the new additions */
	/*	The "splitFrontArc" already should have set up a spoke
		for the new arc -- no circle event will ever be generated
		for the middle/new arc. */

	tryToSchedule(front, schedule, topHalf, (Real)(XVal(matchPoint)));
	tryToSchedule(front, schedule, bottomHalf, (Real)(XVal(matchPoint)));
}

void
mergeVorVertexLists(int	fwdCount, int bwdCount, int *fwdList, int *bwdList,
		int middleVal, int endVal, int *targetCount, int *targetArray)
{
	int		count, i;

	count = *targetCount;

	for (i = 0; i < fwdCount; count++, i++)
		targetArray[count] = fwdList[i];

	if (middleVal >= 0) {
		targetArray[count++] = middleVal;
		*targetCount += 1;
	}

	for (i = bwdCount - 1; i >= 0; count++, i--)
		targetArray[count] = bwdList[i];

	if (endVal >= 0) {
		targetArray[count++] = endVal;
		*targetCount += 1;
	}

	*targetCount += fwdCount + bwdCount;
}

void
mergeFrontVorVertexLists(int fwdCount, int bwdCount, int *fwdList, 
	int *bwdList, int newIndex, int *moveToCount, int *moveToList)
{
	int	i, temp, count;

	temp = fwdCount + bwdCount;
	if (newIndex >= 0)
		temp += 1;
	for (i = *moveToCount-1; i >= 0 ; i--) {
		moveToList[i + temp] = moveToList[i];
	}

	for (count = 0; count < fwdCount; count++)
		moveToList[count] =fwdList[count];
	if (newIndex >= 0)
		moveToList[count++] = newIndex;
	for (i = bwdCount - 1; i >= 0; count++, i--)
		moveToList[count] = bwdList[i];
	*moveToCount += temp;
}

void
processCircleEvent(scheduleInfo *item, link_ref *front, HEAP_Heap schedule)
{
	boolean			dontCare;
	scheduleInfo	*deadInfo;
	frontInfo		*deletedFront;
	link_node		*holdIt;
	frontInfo		*frontArc, *topArc, *bottomArc;
	int				index, i;
	spokeInfo		topSpoke, bottomSpoke;
	Pt				*at1, *at2, *at3, *vor;

#ifdef DEBUG_FLOW
	printf("swp: Circle at x = %2.2f y = %2.2f, to middle point "
			"(%2.1f, %2.1f)\n",
		(float) XVal(item->eventCentre), (float) YVal(item->eventCentre),
		(float)XVal(item->midSpoke.attachment), 
		(float)YVal(item->midSpoke.attachment));
#endif

	/*	Get all the players in the circle event. */

	dontCare = getLinkInfo (item->frontArcs[0], (void **)(&topArc));
	dontCare = deleteLink(front, &(item->frontArcs[1]), 
					(void **) (&deletedFront));
	dontCare = getLinkInfo (item->frontArcs[2], (void **)(&bottomArc));

	/*	Register the Voronoi vertex before we go any farther. */

	findSpoke(&(item->eventCentre), topArc->generator, &topSpoke);
	findSpoke(&(item->eventCentre), bottomArc->generator, &bottomSpoke);
	index = recordVoronoiVertex (&(item->eventCentre), &topSpoke, 
		&(item->midSpoke), &bottomSpoke);

	/*	Add the Voronoi index to the other two front arcs. */

	topArc->bottomVor[topArc->bottomCount++] = index;
	bottomArc->topVor[bottomArc->topCount++] = index;

	/*	Spew out debuging information as necessary. */

	if (demoPass == True) {
#ifdef Graphics
		/*	Draw the Voronoi vertex and the spokes */

		if (showDebugInfo == True) {
			Real	radius;

			pointDistance (&(item->eventCentre), &(item->midSpoke.attachment),
				&radius);
			circlex = XVal(item->eventCentre);
			circley = YVal(item->eventCentre);
			circlerad = (Real) radius;
			redraw();
		}

#else
		/*	Just print out the vertex in text form to check manually */

		printf ("     Voronoi vertex at %3.1f %3.1f to middle point "
			"(%2.0f, %2.0f)\n", 
			(float)XVal(item->eventCentre), (float)YVal(item->eventCentre), 
			(float)XVal(item->midSpoke.attachment), 
			(float)YVal(item->midSpoke.attachment));
#endif
	}

	/*	Move out all the information in the disappearing front arc
		to its counterparts in the sweep front. */

	/*	Remove the deleted front arc from the sweep front.  Merge any
		list of Voronoi vertices that we have already found. */

	if (deletedFront->prev != NULL) {
		mergeFrontVorVertexLists(deletedFront->bottomCount,
			deletedFront->topCount, deletedFront->bottomVor,
			deletedFront->topVor, index, &(deletedFront->prev->bottomCount), 
			deletedFront->prev->bottomVor);
	}
	else if (deletedFront->next != NULL) {
		mergeFrontVorVertexLists( deletedFront->topCount, 
			deletedFront->bottomCount, deletedFront->topVor, 
			deletedFront->bottomVor, index, &(deletedFront->next->topCount), 
			deletedFront->next->topVor);
	}
	else {
		/*	The site no longer contributes to the front so we can
			store all the Voronoi points in the site itself. */

		mergeVorVertexLists(deletedFront->bottomCount,
			deletedFront->topCount, deletedFront->bottomVor, 
			deletedFront->topVor, index, -1, 
			&(deletedFront->generator->voronoiCount),
			deletedFront->generator->voronoiList);
	}

	/*	Put the cores and the spokes into a quad edge data structure.
		This means that the points have to be stored explicitly
		somewhere to be accessed later. */

	at1 = reservePointStore();
	at2 = reservePointStore();
	at3 = reservePointStore();
	vor = reservePointStore();
	PointAssign(*at1, topSpoke.attachment);
	PointAssign(*at2, item->midSpoke.attachment);
	PointAssign(*at3, bottomSpoke.attachment);
	PointAssign(*vor, item->eventCentre);

	/*	Nuke the front arc from the link list for the deleted arc */

	if (deletedFront->prev != NULL)
		deletedFront->prev->next = deletedFront->next;
	if (deletedFront->next != NULL)
		deletedFront->next->prev = deletedFront->prev;

	/*	Clean up the mess in neighbouring front arcs left by
		the one arc disappearing. */

	/*	Remove last vestiges of this circle event from the front. */

	topArc->atTopRef = HEAP_NullHeapId;
	bottomArc->atBottomRef = HEAP_NullHeapId;

	/*	Unscheduling any upcoming events associated with
		the deleted front arc. */

	if (HEAP_PopNamed(schedule, deletedFront->atTopRef,
		(Ptr *)(&deadInfo)) == True) {

#ifdef DEBUG_FLOW
	printf ("swp: circle unscheduled at x = %f (%d)\n", 
		XVal(deadInfo->eventPt), deletedFront->atTopRef);
#endif

		killSchedule(&deadInfo);
		bottomArc->deathRef = HEAP_NullHeapId;
		if ((holdIt = nextLink(front, item->frontArcs[2])) != NULL) {
			getLinkInfo (holdIt, (void **)(&frontArc));
			frontArc->atBottomRef = HEAP_NullHeapId;
		}
	}

	if (HEAP_PopNamed(schedule, deletedFront->atBottomRef,
		(Ptr *)(&deadInfo)) == True) {

#ifdef DEBUG_FLOW
	printf ("swp: circle unscheduled at x = %f (%d)\n", 
		XVal(deadInfo->eventPt), deletedFront->atBottomRef);
#endif

		killSchedule(&deadInfo);
		topArc->deathRef = HEAP_NullHeapId;
		if ((holdIt = prevLink(front, item->frontArcs[0])) != NULL) {
			getLinkInfo (holdIt, (void **)(&frontArc));
			frontArc->atTopRef = HEAP_NullHeapId;
		}
	}

	/*	Finally, schedule new events for the neighbours of the deleted
		arc. */

	tryToSchedule(front, schedule, item->frontArcs[0], XVal(item->eventPt));
	tryToSchedule(front, schedule, item->frontArcs[2], XVal(item->eventPt));

	if (deletedFront != NULL)
		killFront(&deletedFront);
}

void
fillFirstFrontArc(scheduleInfo *item, frontInfo *arc)
{
	arc->generator = item->poly[0];
	arc->deathRef = HEAP_NullHeapId;
	arc->atTopRef = HEAP_NullHeapId;
	arc->atBottomRef = HEAP_NullHeapId;

	arc->prev = NULL;
	arc->next = NULL;
	arc->topCount = 0;
	arc->bottomCount = 0;

	/*	Set up a backward-pointing spoke for the polygon. */

	arc->spoke.attachPolygon = item->poly[0];
	PointAssign(arc->spoke.attachment, item->eventPt);
	PointAssign(arc->spoke.otherPt, item->eventPt);
	arc->spoke.otherPt.x -= arc->spoke.otherPt.w;
	arc->spoke.attachIndex = 2*(item->poly[0])->leftmost;

	/*	All the fronts will advance at the same rate so a 
		horizontal line through the leftmost point should do for
		now. */

	arc->lineThroughFrontArc.w = (item->eventPt).y;
	arc->lineThroughFrontArc.x = 0;
	arc->lineThroughFrontArc.y = -(item->eventPt).w;
}

Real
startTheSweepFront(HEAP_Heap schedule, link_ref *front)
{
	boolean			dontCare, peekOkay;
	scheduleInfo	*item;
	Real			firstPos;
	frontInfo		*arc, *lastarc;
	link_node		*arcRef, *lastArcRef;

	if (HEAP_Size(schedule) != 0) {
		dontCare = HEAP_PopTop (schedule, (Ptr *)(&item));

		/*	Any item I pull off now is a new site event -- nothing
			else should be in the schedule. */

		firstPos = XVal(item->eventPt);
#ifdef DEBUG_SWEEP
		printf ("swp: First front arc at position %f %f\n",
			XVal(item->eventPt), YVal(item->eventPt));
#endif

		/*	This is the first arc in the front -- easy to add */

		arc = newFront();
		fillFirstFrontArc(item, arc);

		dontCare = addAfterLink(front, NULL, (void *)arc, &arcRef);
		lastarc = arc;
		lastArcRef = arcRef;

		killSchedule(&item);

		/*	Add in whatever arcs remain at the same x position. */

		peekOkay = HEAP_PeekTop(schedule, (Ptr *)(&item));
		while ((Zero(firstPos - XVal(item->eventPt))) && peekOkay) {
			dontCare = HEAP_PopTop(schedule, (Ptr *)(&item));

#ifdef DEBUG_SWEEP
			printf ("swp: Extra starting arc at position %f %f\n",
				XVal(item->eventPt), YVal(item->eventPt));
#endif

			/*	The arcs should appear in decreasing order by
				y-coordinate. */

			arc = newFront();
			fillFirstFrontArc(item, arc);
			arc->topCount = 1;
			arc->topVor[0] = 0;

			peekOkay = addAfterLink(front, lastArcRef, (void *)arc, &arcRef);
			lastarc = arc;
			lastArcRef = arcRef;

			killSchedule(&item);

			dontCare = HEAP_PeekTop(schedule, (Ptr *)(&item));
		}
		lastarc->topCount = 0;
	}
	else
		firstPos = 0.0;

	return(firstPos);
}

void
cleanUpSweepFront(link_ref *front)
{
	frontInfo	*frontItem, *headInfo, *tailInfo;
	link_node	*holdIt, *discardIt, *head, *tail;

	/*	Skip the first node in the list -- it is split as the
		first and last items in the sweep front. */

	holdIt = front->head;
	if (holdIt != NULL) {
		holdIt = nextLink(front, holdIt);

		while (nextLink(front, holdIt) != NULL) {
			getLinkInfo (holdIt, (void **)(&frontItem));

			mergeVorVertexLists(frontItem->bottomCount,
				frontItem->topCount, frontItem->bottomVor,
				frontItem->topVor, 0, -1,
				&(frontItem->generator->voronoiCount),
				frontItem->generator->voronoiList);

			discardIt = holdIt;
			holdIt = nextLink (front, discardIt);
			deleteLink (front, &discardIt, (void **)(&frontItem));
			killFront(&frontItem);
		}

		/*	Still need to clean up the head/tail front items. */

		tail = holdIt;
		head = front->head;
		getLinkInfo (tail, (void **)(&tailInfo));
		getLinkInfo (head, (void **)(&headInfo));

		if (headInfo->generator == tailInfo->generator) {

			mergeVorVertexLists(headInfo->bottomCount, headInfo->topCount, 
				headInfo->bottomVor, headInfo->topVor, -1, 0,
				&(headInfo->generator->voronoiCount),
				headInfo->generator->voronoiList);

			mergeVorVertexLists(tailInfo->bottomCount, tailInfo->topCount, 
				tailInfo->bottomVor, tailInfo->topVor, -1, -1,
				&(tailInfo->generator->voronoiCount),
				tailInfo->generator->voronoiList);
		}
		else {
			mergeVorVertexLists(headInfo->bottomCount,
				headInfo->topCount, headInfo->bottomVor,
				headInfo->topVor, -1, 0,
				&(headInfo->generator->voronoiCount),
				headInfo->generator->voronoiList);

			mergeVorVertexLists(tailInfo->bottomCount,
				tailInfo->topCount, tailInfo->bottomVor,
				tailInfo->topVor, -1, 0,
				&(tailInfo->generator->voronoiCount),
				tailInfo->generator->voronoiList);
		}

		deleteLink (front, &head, (void **)(&headInfo));
		killFront(&headInfo);

		deleteLink (front, &tail, (void **)(&tailInfo));
		killFront(&tailInfo);
	}
}

void
createSweepLine()
{
	Pt	image[3];

	image[0].w = 1.0;
	image[0].x = (Coordinate) -SweepLimits;
	image[0].y = (Coordinate) (-1 * SweepLimits);
	image[1].w = 1.0;
	image[1].x = (Coordinate) -SweepLimits;
	image[1].y = (Coordinate) SweepLimits;
	sweepLine = newPolygon(2, image);

}

void
advanceSweepLine(Real newPos)
{
	sweepLine->points[0].x = newPos;
	sweepLine->points[1].x = newPos;
}

void
destroySweepLine()
{
	killPolygon(&sweepLine);
}


void
sweep (Pgon **polyList, int numPoly, int delayCoeff)
{
	HEAP_Heap		schedule, polySched;
	link_ref		*front;
	scheduleInfo	*nextPoly, *item;
	boolean			dontCare;
	
	/* Initialize all data structures */
	
	schedule = HEAP_Allocate(2*numPoly, compareHeapKeys, "circles");
	polySched = HEAP_Allocate(numPoly+1, compareHeapKeys, "Polys");
	front = initLink();
	swFront = front;
	delayFactor = Max(0.0, delayCoeff);

	/*	Get the memory routines for the schedule and front started. */

	startSchedule(2*numPoly);
	startFront(2*numPoly);

	/*	Keep a representation of the sweepline around for everybody
		to use.  The x value should only change as a result of 
		this sweep routine. */

	createSweepLine();
	getSweeplineTan(&sweepTangent);

	if ((demoPass == True) && ((showDebugInfo == True) || (autoDebug == True))) 
		inSweep = True;

	if (scheduleNewSites(polySched, polyList, numPoly) == True) {

		/*	Start the sweep front with all the sites that have a 
			common leftmost point. */

		sweepPosition = startTheSweepFront(polySched, front);
		steadyStateDebuggingInfo(front, polySched, schedule);

		/*	Keep processing while events are happening.  We assume
			that no events occur at infinity */

		item = NULL;
		dontCare = HEAP_PeekTop (polySched, (Ptr *)(&nextPoly));
		while ((nextPoly != NULL) || (item != NULL)) {
			clearAnimationInfo();
			animateSweepLine(nextPoly, item);

			if ((item == NULL) || ((nextPoly != NULL) && 
				(!Less(XVal(item->eventPt), XVal(nextPoly->eventPt))))) {

				dontCare = HEAP_PopTop (polySched, (Ptr *)(&nextPoly));
				advanceSweepLine(XVal(nextPoly->eventPt));
				processNewSite(nextPoly, front, schedule);
				killSchedule(&nextPoly);
				dontCare = HEAP_PeekTop (polySched, (Ptr *)(&nextPoly));
			}
			else {
				dontCare = HEAP_PopTop (schedule, (Ptr *)(&item));
				advanceSweepLine(XVal(item->eventPt));
				processCircleEvent(item, front, schedule);
				killSchedule(&item);
			}
			dontCare = HEAP_PeekTop (schedule, (Ptr *)(&item));
			steadyStateDebuggingInfo(front, polySched, schedule);

#ifdef Graphics
			if ((demoPass == True) && (showDebugInfo == True)) 
				waitForStep();
#endif
		}

		clearAnimationInfo();
		sweepPosition = 130.0;
		inSweep = False;

		/*	Now that the sweep is done, empty out the sweep front,
			storing the Voronoi vertices for each of the remaining sites
			(all of which are on the convex hull) with the polygon itself.
			Mark the "infinite" Voronoi vertex by a non-existent index. */

		cleanUpSweepFront(front);
	}

	showVerticesDebugging(numPoly, polyList);

	destroySweepLine();
	HEAP_Free(schedule);
	HEAP_Free(polySched);
	killLink(&front);

	/*	Finish up the memory routines for the schedule and front. */

	endSchedule();
	endFront();

}

